package com.otheima.quitesort;

import java.util.Arrays;

public class Test {//快排代码实现

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] arr = {1, 50, 90, 65, 2, 5, 6, 8, 75};
        //快排后打印数组
        quiteSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

        long end = System.currentTimeMillis();
        System.out.println("时间：" + (end - start));
    }

    public static void quiteSort(int[] arr, int left, int right) {
        //停止条件
        if(left>right){
            return;
        }

        int left0 = left;
        int right0 = right;

        //计算基准数
        int baseNumber = arr[left0];
        while (left != right) {//当左指针与右指针不重叠，持续循环
            while (arr[right]>=baseNumber && right >left) {//在右边找到比基准数小的，左指针就停下
                right--;
            }
            while (arr[left] <= baseNumber && right > left) {//在左边找到比基准数大的，左指针就停下
                left++;
            }
            //交换两个值的位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        //基准数归位
        int temp = arr[left0];
        arr[left0] = arr[left];
        arr[left] = temp;



        //基准数左边实现
        quiteSort(arr,left0,left-1);
        quiteSort(arr,left+1,right0);
    }
}
